package com.fanshuai.algorithms.dynamic;

/**
 * 博弈问题
 * 其核心思路是在二维 dp 的基础上使用元组分别存储两个人的博弈结果。
 */
public class Compete {
    static class Pair {
        public int first;
        public int second;

        @Override
        public String toString() {
            return "Pair{" +
                    "first=" + first +
                    ", second=" + second +
                    '}';
        }
    }

    /**
     * 你和你的朋友面前有一排石头堆，用一个数组 piles 表示，piles[i] 表示第 i 堆石子有多少个。
     * 你们轮流拿石头，一次拿一堆，但是只能拿走最左边或者最右边的石头堆。所有石头被拿完后，谁拥有的石头多，谁获胜。
     * 假设两人都很聪明，请你设计一个算法，返回先手和后手的最后得分（石头总数）之差。
     *
     * 动态规划解法：
     * dp table: dp[i][j][first or second] 表示石头堆的子集piles[i..j], first表示先手获得最高分数，second表示后手获得最高分数
     * 状态转移方程：
     * dp[i][j].first = max(piles[i] + dp[i+1][j].second, piles[j] + dp[i][j-1].second)
     * dp[i][j].second = max(dp[i+1][j].first, dp[i][j-1].first)
     *
     * bad case: 对任意 0<=i<n，dp[i][i].first=piles[i], dp[i][j].second=0
     *
     *
     * @param piles 石头堆，piles[i] 表示第 i 堆石子有多少个
     * @return
     */
    public static int stone(int[] piles) {
        int len = piles.length;
        Pair[][] dp = new Pair[len][len];

        for (int i = 0; i < len; i++) {
            dp[i][i] = new Pair();
            dp[i][i].first = piles[i];
            dp[i][i].second = 0;
        }

        /**
         * 按矩形对角线顺序求dp table
         */
        for (int l = 2; l <= len; l++) {
            for (int i = 0; i <= len - l; i++) {
                int j = i + l - 1;
                dp[i][j] = new Pair();

                int left = piles[i] + dp[i + 1][j].second;
                int right = piles[j] + dp[i][j - 1].second;
                /**
                 * 博弈问题，dp table元素为元组，元组每个元素的取值，取决于状态选择
                 */
                if (left > right) {
                    dp[i][j].first = left;
                    dp[i][j].second = dp[i + 1][j].first;
                } else {
                    dp[i][j].first = right;
                    dp[i][j].second = dp[i][j - 1].first;
                }
            }
        }

        Pair pair = dp[0][len - 1];
        System.out.println(pair);

        return pair.first - pair.second;
    }

    static class Ticket {
        int hold; //持有状态
        int unhold; //未持有状态

        @Override
        public String toString() {
            return "Ticket{" +
                    "hold=" + hold +
                    ", unhold=" + unhold +
                    '}';
        }
    }

    /**
     * 股票买卖问题
     * 给定一个数组，第i个元素是一支股票在第i天的价格，假设最多能进行k场交易，计算能获取的最大利润
     * 不能同时参与多笔交易，再次购买前需要出售之前的股票
     *
     * 动态规划解法：
     * 问题状态：i表示天数，k表示已进行了k次交易，rest=[0,1]，0表示不持有股票，1表示持有股票
     * 选择：buy sell rest
     * buy表示买入，rest从0变为1
     * sell表示卖出,rest从1变为0
     * rest表示不交易，rest不变
     *
     * dp[i][k][0 or 1] 表示第i天，已进行了k次交易，不持有或持有股票状态的最大利润
     *
     * 状态转移方程：
     * dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + stocks[i-1])
     * dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - stocks[i-1])
     *
     * bad case:
     * dp[0][k][0] = 0  第0天
     * dp[0][k][1] = -inf
     *
     * dp[i][0][0] = 0  第0笔交易
     * dp[i][0][1] = -inf
     *
     * 求dp[n][k][0]
     * @param stocks  股票价格
     * @param k  交易数
     * @return
     */
    public static int maxProfix(int[] stocks, int k) {
        int days = stocks.length;
        Ticket[][] dp = new Ticket[days + 1][k + 1];

        //bad case
        for (int i = 0; i <= days; i++) {
            dp[i][0] = new Ticket();
            dp[i][0].unhold = 0;
            dp[i][0].hold = Integer.MIN_VALUE;
        }
        for (int j = 0; j <= k; j++) {
            dp[0][j] = new Ticket();
            dp[0][j].unhold = 0;
            dp[0][j].hold = Integer.MIN_VALUE;
        }

        //dp table
        for (int i = 1; i <= days; i++) {
            for (int j = 1; j <= k; j++) {
                dp[i][j] = new Ticket();
                dp[i][j].unhold = Math.max(dp[i - 1][k].unhold, dp[i - 1][k].hold + stocks[i - 1]);
                dp[i][j].hold = Math.max(dp[i - 1][k].hold, dp[i - 1][k - 1].unhold - stocks[i - 1]);

                System.out.println(String.format("dp[%d][%d]=%s", i, j, dp[i][j]));
            }
        }

        return dp[days][k].unhold;
    }

    public static void main(String[] args) {
        int[] piles = {3, 9, 1, 2};
        System.out.println(stone(piles));

        int[] stock1 = {2, 4, 1};
        int[] stock2 = {3, 2, 6, 5, 0, 3};

        System.out.println(maxProfix(stock1, 2));
        System.out.println(maxProfix(stock2, 2));
    }
}
